#include <string>
#include <vector>
using namespace std;
/*
 * @lc app=leetcode.cn id=22 lang=cpp
 *
 * [22] 括号生成
 */

// @lc code=start
class Solution {
public:
    // 
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        dfs(res, 0, 0, n, "");
        return res;
    }

    void dfs(vector<string> & res, int l, int r, int t, string x) {
        if (l == t && r == t) {
            res.push_back(x); return;
        }
        if (r < l) {
            x.push_back(')'); dfs(res, l, r + 1, t, x);
            x.pop_back();
            if (l < t) {
                x.push_back('(');
                dfs(res, l + 1, r, t, x); x.pop_back();
            }
        } else {
            x.push_back('(');
            dfs(res, l + 1, r, t, x);
            x.pop_back();
        }
    }
};
// @lc code=end

